package von.seiji.cn.other;

import cn.hutool.core.collection.ListUtil;
import cn.hutool.core.lang.Assert;
import cn.hutool.core.lang.Dict;
import cn.hutool.core.util.StrUtil;
import cn.hutool.crypto.digest.DigestUtil;
import com.google.common.collect.Lists;
import com.google.common.collect.Maps;
import com.google.common.collect.Sets;
import org.junit.Test;

import java.util.*;
import java.util.function.Predicate;
import java.util.function.Supplier;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
import java.util.stream.Stream;

public class Railway1 {

    static Map<String, ArrayList<String>> lineMap = Maps.newHashMap();

    //线路交点名称
    static List<ArrayList<String>> intersectionList = Lists.newArrayList();


    static {

        Dict dict = Dict.of("A", 8, "B", 9, "C", 10, "D", 15);


        intersectionList = Lists.newArrayList(
                Lists.newArrayList("A3", "C1"),
                Lists.newArrayList("A5", "D2"),
                Lists.newArrayList("A6", "B7"),
                Lists.newArrayList("B2", "D7"),
                Lists.newArrayList("B4", "C4"),
                Lists.newArrayList("C2", "D4"),
                Lists.newArrayList("C5", "D11")

        );

        lineMap = Maps.asMap(Sets.<String>newHashSet("A", "B", "C", "D"), input ->
                ((ArrayList<String>) IntStream.range(0, dict.getInt(input)).mapToObj(item -> {
                    String stop = input + item;
                    return intersectionList.stream().filter(item2 -> item2.contains(stop)).findFirst().map(item2 ->
                            DigestUtil.md5Hex(item2.stream().sorted().collect(Collectors.joining()))
                    ).orElseGet(() -> DigestUtil.md5Hex(stop));
                }).collect(Collectors.toList()))
        );

    }


    @Test
    public void testPlan() {

        String start = nameByCode("D12");
        String end = nameByCode("C2");
//        String end = null;

        List<ArrayList<String>> routePlan = planing(start, end);
        routePlan.forEach(System.out::println);
        System.out.println("===================================");

        System.out.println("所有路线简编：");

        routePlan.stream().map(item -> item.stream().map(this::findCode).collect(Collectors.toList())).forEach(System.err::println);


        System.err.println("---------------------测试-----------------------");

        // [{C=[C9, C8, C7, C6, C5D11, B4C4, C3, C2D4, A3C1]}, {A=[A3C1, A2, A1, A0]}]


        List<String> strings = routePlan.get(0);


        System.out.println("***********************************************");


        System.err.println("----------------这个怎么样-----------------");
        detailRoute(strings).entrySet().forEach(item -> {
            item.setValue(item.getValue().stream().map(this::findCode).collect(Collectors.toList()));
            System.out.println(item);
        });
        System.err.println("----------------这个怎么样-----------------");
        detailRoute2(strings).entrySet().forEach(item -> {
            item.setValue(item.getValue().stream().map(this::findCode).collect(Collectors.toList()));
            System.out.println(item);
        });

        System.err.println("----------------这个怎么样-----------------");
        detailRoute3(strings).entrySet().forEach(item -> {
            item.setValue(item.getValue().stream().map(this::findCode).collect(Collectors.toList()));
            System.out.println(item);
        });

        System.err.println("--------------------------------------------");

        System.out.println("完整路线简编：");
        routePlan.stream().map(this::optimalLines).forEach(item -> {
            item.forEach(item1 -> item1.entrySet().forEach(item2 -> {
                item2.setValue(item2.getValue().stream().map(this::findCode).collect(Collectors.toList()));
            }));
            System.out.println(item);
        });

        System.out.println("简编路线整合：");

        routePlan.stream().map(this::detailRoute3).forEach(item -> {
            item.entrySet().forEach(item1 -> {
                item1.setValue(item1.getValue().stream().map(this::findCode).collect(Collectors.toList()));
            });
            System.out.println(item);
        });

        Map.Entry<String, List<String>> entry = routePlan.stream().map(this::detailRoute2).map(Map::entrySet)
                .flatMap(Set::stream).min(Comparator.comparingInt(item -> item.getValue().size()))
                .get();
        Map<String, List<String>> collect = Stream.of(entry).collect(Collectors.toMap(Map.Entry::getKey, item ->
            item.getValue().stream().map(this::findCode).collect(Collectors.toList())
        ));
        System.out.println("最优线路：" + collect);


    }


    /**
     * 提取一条路线的完整路线名
     *
     * @param optimalLines
     * @return
     */
    public List<ArrayList<String>> routeLineKey(List<Map<String, List<String>>> optimalLines) {
        Queue<Map<String, List<String>>> queue = Lists.newLinkedList();
        queue.addAll(optimalLines);
        Map<String, List<String>> poll = queue.poll();

        return routeLineKey(queue, () ->
                poll.entrySet().stream()
                        .map(Map.Entry::getKey).map(Lists::newArrayList).collect(Collectors.toList())
        );

    }

    private List<ArrayList<String>> routeLineKey(Queue<Map<String, List<String>>> queue, Supplier<List<ArrayList<String>>> supplier) {
        List<ArrayList<String>> arrayLists = supplier.get();
        return queue.isEmpty() ? arrayLists
                : routeLineKey(queue, () ->
                arrayLists.stream().flatMap(item
                        -> queue.poll().entrySet().stream()
                        .map(Map.Entry::getKey).map(lineName -> appendToList(item, lineName))
                ).collect(Collectors.toList()));
    }

    /**
     * 路线推导
     *
     * @param start
     * @param end
     * @return
     */
    public List<ArrayList<String>> planing(String start, String end) {
        Assert.notBlank(start, "起始点不能为空");
        Assert.isTrue(StrUtil.isEmpty(end)
                || !start.equals(end), "结束点要么为空，否则不能和其实点相同");
        List<ArrayList<String>> planing = planing(end, candidates -> candidates.stream().allMatch(item ->
                        item.contains(end) || findNextLines(item).isEmpty()
                )
                , () ->
                        Optional.of(start).map(item ->
                                findLine(item).stream().flatMap(beginLine -> {
                                    //判断终点是否在该线上(不管起点是终点是否同线，都应该继续，同线不代表最优线路)
                                    Set<String> hubs = endPoint(beginLine, item, end);
                                    return hubs.stream().map(hub -> Lists.newArrayList(item, hub));
                                }).collect(Collectors.toList())
                        ).orElse(null)
        );
        return planing;

    }

    private List<ArrayList<String>> planing(String destination, Predicate<List<ArrayList<String>>> end, Supplier<List<ArrayList<String>>> supplier) {
        List<ArrayList<String>> candidates = supplier.get();
        if (!candidates.isEmpty()) {
            return end.test(candidates) ? Optional.ofNullable(destination).map(item ->
                    // 过滤包含终点的线路
                    candidates.stream()
                            .filter(line -> line.contains(item)).collect(Collectors.toList())
            ).orElse(candidates)
                    : planing(destination, collect -> end.test(candidates) || candidates.size() == collect.size()
                    , () ->
                            candidates.stream().flatMap(candidate -> {
                                List<String> nextLines = nextLine(candidate);

                                return !candidate.contains(destination) && !nextLines.isEmpty() ? nextLines.stream().flatMap(nextLine -> {

                                    String last = Lists.newLinkedList(candidate).getLast();
                                    Set<String> usedLines = findUsedLines(candidate);
                                    //判断终点是否在该线上
                                    Set<String> hubs = endPoint(nextLine, last, destination);
                                    /**
                                     * 旧版：
                                     * 1.枢纽所在的所有可能的线不能是已经路过的线
                                     * 2.不仅该枢纽不能在以路过的线上，而且该点到枢纽中的站点也不能经过以路过的线
                                     * 3.这些条件造成了一个重大的问题：虽然在这里作为路线终止的条件，却不能成为方法递归结束的条件
                                     * 新版：嘻嘻，放弃之前的定义重新思考
                                     * 1.根据路过的点判断是否值得吧
                                     */
                                    List<String> collect = hubs.stream().filter(item ->
                                            availableNext(candidate, item)
                                    ).collect(Collectors.toList());


                                  /*
                                  废除一下过滤
                                  List<String> collect = hubs.stream().filter(hub ->
                                            // 枢纽所在的所有可能的线不能是已经路过的线
                                            findLine(hub).stream().allMatch(possibleLine ->
                                                    !usedLines.contains(possibleLine)
                                            )).filter(hub ->
                                            // 不仅该枢纽不能在以路过的线上，而且该点到枢纽中的站点也不能经过以路过的线
                                            //这些条件造成了一个重大的问题：虽然在这里作为路线终止的条件，却不能成为方法递归结束的条件
                                            summaryStop(last, hub).entrySet().stream().map(Map.Entry::getValue).anyMatch(possibleLine ->
                                                    possibleLine.stream().filter(stop -> !last.equals(stop)).allMatch(possibleStop ->
                                                            findLine(possibleStop).stream().noneMatch(usedLines::contains)
                                                    )
                                            )
                                    ).collect(Collectors.toList());*/

//                            return collect.stream().map(hub -> appendToList((ArrayList<String>) candidate.clone(), hub));
                                    return collect.isEmpty()
                                            ? Stream.of((ArrayList<String>) candidate.clone()).map(ArrayList::new)
                                            : collect.stream().map(hub -> appendToList((ArrayList<String>) candidate.clone(), hub));
                                }) : Stream.of((ArrayList<String>) candidate.clone()).map(ArrayList::new);

                            }).collect(Collectors.toList())
            );

        }
        return candidates;
    }


    <E> ArrayList<E> appendToList(List<E> elements, E... elem) {

        ArrayList<E> es1 = Lists.newArrayList(elements);
        Arrays.stream(elem).filter(Objects::nonNull).forEach(es1::add);
        return es1;
    }

    <E> ArrayList<E> comboToList(List<E> elements, List<E>... source) {

        ArrayList<E> es1 = Lists.newArrayList(elements);
        Arrays.stream(source).forEach(es1::addAll);
        return es1;
    }

    /**
     * 和一样#detailRoute方法
     *
     * @param line
     * @return
     */
    public Map<String, List<String>> detailRoute3(List<String> line) {
        List<Map<String, List<String>>> maps = optimalLines(line);
        Queue<Map<String, List<String>>> queue = new LinkedList<>();
        queue.addAll(maps);
        return detailRoute3(() -> queue.poll(), queue);
    }

    private Map<String, List<String>> detailRoute3(Supplier<Map<String, List<String>>> analyse, Queue<Map<String, List<String>>> queue) {
        Map<String, List<String>> map = analyse.get();
        if (queue.isEmpty()) {
            return map;
        } else {
            return detailRoute3(() -> {
                Map<String, List<String>> poll = queue.poll();

                return map.entrySet().stream().flatMap(item ->
                        poll.entrySet().stream().collect(Collectors.toMap(entry ->
                                        item.getKey() + entry.getKey()
                                , entry ->
                                        comboToList(item.getValue(), entry.getValue())
                                                .stream().distinct().collect(Collectors.toList())
                        )).entrySet().stream()
                ).collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue));

            }, queue);
        }
    }

    /**
     * 将一段(减)路线以路线名组合为key，经过的所有点组成的集合为value
     *
     * @param line
     * @return
     */
    public Map<String, List<String>> detailRoute(List<String> line) {
        List<Map<String, List<String>>> maps = optimalLines(line);
        List<Map<String, List<String>>> collect = Stream.of(maps).flatMap(List::stream).collect(Collectors.toList());
        return collect.stream().reduce((result, current) ->
                result.entrySet().stream().flatMap(entry ->
                        current.entrySet().stream().collect(
                                Collectors.toMap(entry1 -> entry.getKey() + entry1.getKey(), entry1 ->
                                        comboToList(entry.getValue(), entry1.getValue())
                                                .stream().distinct().collect(Collectors.toList())
                                )
                        ).entrySet().stream()
                ).collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue))
        ).orElse(null);
    }

    /**
     * 和上面的一样#detailRoute方法
     *
     * @param line
     * @return
     */
    public Map<String, List<String>> detailRoute2(List<String> line) {

        List<Map<String, List<String>>> maps = optimalLines(line);
        List<ArrayList<String>> arrayLists = routeLineKey(maps);
        return arrayLists.stream().collect(Collectors.toMap(item ->
                        item.stream().collect(Collectors.joining())
                , item ->
                        item.stream().flatMap(item1 -> {
                            int i = item.indexOf(item1);
                            Map<String, List<String>> map = maps.get(i);
                            return map.get(item1).stream();
                        }).distinct().collect(Collectors.toList())
        ));
    }


    /**
     * 根据某个站名求路线名
     *
     * @return
     */
    public List<String> findLine(String stop) {

        return lineMap.entrySet().stream()
                .filter(item -> item.getValue().contains(stop))
                .map(Map.Entry::getKey).collect(Collectors.toList());

    }

    @Test
    public void testFindLine() {
        List<String> d3F4 = findLine(DigestUtil.md5Hex("D3F4"));
        System.out.println("d3F4 = " + d3F4);
        ArrayList<String> strings = Lists.newArrayList("D1", "A");
        boolean b = d3F4.stream().noneMatch(strings::contains);
        System.out.println("b = " + b);
    }

    /**
     * 根据已经通过的站点找到下一站所在的路线
     * 接下来的路线不能是之前已路过的，但是！！！
     * 对U型和环形路线不适用了
     *
     * @param stops
     * @return
     */
    @Deprecated
    public List<String> findNextLines(List<String> stops) {

        String last = Lists.newLinkedList(stops).getLast();

        //最后这个站点所在的路线（可能有多个，即交汇处）
        List<String> lastLineNames = findLine(last);


        List<String> passedLineNames = optimalLines(stops).stream()
                .map(Map::entrySet).flatMap(Set::stream)
                .map(Map.Entry::getKey).collect(Collectors.toList());

        return lastLineNames.stream().filter(item
                -> !passedLineNames.contains(item))
                .collect(Collectors.toList());
    }

    // 升级（只保证下一条路线不能（多条的话就是不包含）是已路过的最后一条（或多条））
    public List<String> nextLine(List<String> stops) {
        List<Map<String, List<String>>> maps = optimalLines(stops);
        List<String> collect = Lists.newLinkedList(maps).getLast().entrySet().stream()
                .map(Map.Entry::getKey).collect(Collectors.toList());
        String last = Lists.newLinkedList(stops).getLast();
        return findLine(last).stream().filter(item
                -> !collect.contains(item)).collect(Collectors.toList());
    }


    @Test
    public void testFindNextLine() {
        List<String> nextLines = findNextLines(nameByCodes("C6", "D11", "B2", "B7", "A0"));
        System.out.println("nextLine = " + nextLines);
        boolean b = availableNext(nameByCodes("C6", "D11", "B2", "B7", "A3"), nameByCode("C2"));
        System.out.println("b = " + b);
    }

    /**
     * 根据简编获取站名（如A1(实际编码：A1D4)）
     */
    public String nameByCode(String code) {
        return DigestUtil.md5Hex(codeToRel(code));
    }


    public List<String> nameByCodes(String... codes) {
        return Arrays.stream(codes).map(item
                -> DigestUtil.md5Hex(codeToRel(item))).collect(Collectors.toList());
    }


    /**
     * 根据简编获取实际编码（如A1(实际编码：A1D4)）
     */
    public String codeToRel(String code) {
        return intersectionList.stream().filter(item -> item.contains(code)).findAny().map(item ->
                item.stream().sorted().collect(Collectors.joining())
        ).orElse(code);
    }

    /**
     * 根据已经通过的站点找到以乘坐过的路线
     * 只是踩点而已，算不上是在线上走过！！！
     *
     * @param stops
     * @return
     */
    public Set<String> findUsedLines(List<String> stops) {
/*
        Map<String, Long> collect = stops.stream().map(this::findLine)
                .flatMap(List::stream).collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));
        return collect.entrySet().stream().filter(item -> item.getValue() > 1).map(Map.Entry::getKey).collect(Collectors.toList());*/
        return IntStream.range(0, stops.size() - 1).mapToObj(item ->
                optimalLine(stops.get(item), stops.get(item + 1))
                        .keySet()
        ).flatMap(Set::stream).collect(Collectors.toSet());
    }

    @Test
    public void testFindUsedLines() {
        ArrayList<String> strings = Lists.newArrayList("C9", "C5", "D4", "A3", "A7");
        List<String> collect = strings.stream().map(this::nameByCode).collect(Collectors.toList());
        System.out.println("collect = " + collect);
        findUsedLines(collect).forEach(System.out::println);
    }

    /**
     * 根据路线获取线路枢纽(不包括指定的站)
     * 1.优化current到该交汇点处的最优线路必须为lineName
     * 2.不能包含当前点
     * 3.若重点在该路线上，那么到其他的交汇点的间隔数不能比到终点的长
     */
    public Set<String> endPoint(String lineName, String current, String end) {
        ArrayList<String> stops = lineMap.get(lineName);

        Set<String> collect = stops.stream().filter(item ->
                (item.equals(end) ||
                        //求出交汇点
                        lineMap.entrySet().stream().filter(link ->
                                !lineName.equals(link.getKey()))
                                .map(Map.Entry::getValue).anyMatch(otherLine -> otherLine.contains(item))
                                && !current.equals(item)

                ) &&
                        optimalLine(current, item).containsKey(lineName)
        ).collect(Collectors.toSet());

        //第二道过滤
        if (collect.contains(end)) {
            return collect.stream().filter(item ->
                    item.equals(end) ||
                            optimalLine(current, end).get(lineName).size() > optimalLine(current, item).get(lineName).size()
            ).collect(Collectors.toSet());
        }
        return collect;
    }

    @Test
    public void testFindHubs() {
        Set<String> a = endPoint("A", "C3", null);
        System.out.println("a = " + a);
        System.out.println(a.stream().map(item -> findCode(item)).collect(Collectors.toList()));

    }

    /**
     * 根据站点获取编码
     */
    public String findCode(String stop) {
        List<String> line = findLine(stop);
        String collect = lineMap.entrySet().stream().filter(item -> line.contains(item.getKey()))
                .map(item -> item.getKey().toString() + item.getValue().indexOf(stop))
                .sorted().collect(Collectors.joining());

        return collect;
    }

    @Test
    public void testFindCode() {

        String stop = "d88c146dfafdea37a837778a92415bc2";
        String code = findCode(stop);
        System.out.println("code = " + code);
        System.out.println(ResourceBundle.getBundle("railway").getString(code));
    }


    /**
     * 判断两个站点是否在一条路线上（并获取该路线）
     *
     * @param begin
     * @param end
     * @return
     */
    public Set<String> sameLine(String begin, String end) {
        return lineMap.entrySet().stream().filter(item ->
                item.getValue().containsAll(Lists.newArrayList(begin, end)))
                .map(Map.Entry::getKey).collect(Collectors.toSet());
    }


    @Test
    public void testSameLine() {
        Set<String> line = sameLine("2221a983f5f6216c204666d6e3d84116", "f5586fb769829c4151bec70da6b80756");
        System.out.println("line = " + line);
        Set<String> line1 = sameLine("2221a983f5f6216c204666d6e3d84116", "644ea94bd83e7c53d1ef3a9f8908ee28");
        System.out.println("line1 = " + line1);
        Set<String> line2 = sameLine("f5586fb769829c4151bec70da6b80756", "644ea94bd83e7c53d1ef3a9f8908ee28");
        System.out.println("line2 = " + line2);
    }

    /**
     * 获取包含两个站点间的所有站点（多条选最优）（同一线路）
     */
    public Map<String, List<String>> optimalLine(String begin, String end) {
        Set<String> sameLine = sameLine(begin, end);
        Map<String, List<String>> collect = sameLine.stream().collect(Collectors.toMap(lineName -> lineName, lineName -> {
            List<String> line = lineMap.get(lineName);
            int i = line.indexOf(begin), j = line.indexOf(end);
            return IntStream.range(Math.min(i, j), Math.max(i, j) + 1)
                    .mapToObj(item -> line.get(item)).sorted(Comparator.comparing(item ->
                            Integer.compare(j, i) * line.indexOf(item))).collect(Collectors.toList());
        }));
        int i = collect.entrySet().stream().map(Map.Entry::getValue)
                .mapToInt(List::size).min().orElse(0);
        collect.entrySet().removeIf(item -> item.getValue().size() > i);
        return collect;
    }

    @Test
    public void tesSummaryStop() {
        Map<String, List<String>> stop = optimalLine(DigestUtil.md5Hex(codeToRel("C2")), nameByCode("C5"));
        System.out.println("stop = " + stop);
        stop.keySet().stream().map(item ->
                stop.get(item).stream().map(this::findCode).collect(Collectors.toList())
        ).forEach(System.out::println);
    }

    /**
     * 详细的列出两站之间的路线名和之间的站点
     *
     * @param stops
     * @return
     */
    public List<Map<String, List<String>>> optimalLines(List<String> stops) {
        return IntStream.range(0, stops.size() - 1).mapToObj(item ->
                optimalLine(stops.get(item), stops.get(item + 1))
        ).collect(Collectors.toList());
    }

    @Test
    public void testSummaryAllStop() {
        List<Map<String, List<String>>> maps = optimalLines(nameByCodes("C9", "C6", "C2"));
        maps.forEach(item -> {
            Set<Map.Entry<String, List<String>>> entries = item.entrySet();
            entries.forEach(item1 -> {
                item1.setValue(item1.getValue().stream()
                        .map(this::findCode).collect(Collectors.toList()));
            });
            System.out.println("entries = " + entries);
          /*  item.keySet().stream().map(item1 ->
                    item.get(item1).stream().map(this::findCode).collect(Collectors.toList())
            ).forEach(System.out::println);*/
        });
    }

    //根据已路过的站点判断下一个站点是否可走（避免回头路）
    public boolean availableNext(List<String> stops, String next) {
        List<Map<String, List<String>>> collect = IntStream.range(0, stops.size() - 1).mapToObj(item ->
                optimalLine(stops.get(item), stops.get(item + 1)))
                .filter(item -> item.entrySet().stream().anyMatch(item1 ->
                        findLine(next).contains(item1.getKey()))).collect(Collectors.toList());
        return collect.isEmpty() || collect.stream().allMatch(item ->
                item.entrySet().stream().map(Map.Entry::getValue)
                        .noneMatch(line -> line.contains(next)));
    }

//    public boolean feasible()

    @Test
    public void testEffectiveRegress() {
        boolean b = availableNext(Lists.newArrayList("D14", "C5", "C2").stream().map(this::nameByCode).collect(Collectors.toList())
                , nameByCode("C3"));
        System.out.println("b = " + b);
    }


    /**
     * 根据站点编码生成唯一的站点名称
     */
    @Test
    public void generateStopName() {


        Dict dict = Dict.of("A", 7, "B", 8, "C", 6, "D", 6, "E", 7, "F", 8);

        Map<String, List<String>> asMap = Maps.asMap(Sets.<String>newHashSet("A", "B", "C", "D", "E", "F"), input ->
                IntStream.range(0, dict.getInt(input)).mapToObj(item -> {
                    String stop = input + item;
                    return intersectionList.stream().filter(item2 -> item2.contains(stop)).findFirst().map(item2 -> {
                        String collect = item2.stream().sorted().collect(Collectors.joining());
                        //                    System.out.println("站点<" + collect + ">");
                        //                    System.out.println("#站点编码<"+item1+">交点：" + collect);
                        System.out.println(stop + "=" + DigestUtil.md5Hex(collect));
                        return DigestUtil.md5Hex(collect);
                    }).orElseGet(() -> {
                        //                    System.out.println("#站点<" + item + ">");
                        System.out.println(stop + "=" + DigestUtil.md5Hex(stop));
                        return DigestUtil.md5Hex(stop);
                    });
                }).collect(Collectors.toList())
        );
        asMap.entrySet().stream().forEach(System.out::println);
    }
}
